/**
 *
 * @author Enrico Schroeder
 * Multi-Threaded Implementation von Merge-Sort
 */

package de.fuberlin.inf.alp4.ue1;


public class MultiThreaded {
	// Überladung der sort Funktion für einfacheren Aufruf
    public static long[] mergeSort(long[] list) {
        sort(list, 0, list.length-1);
        return list;
    }

	// merge-sort
    private static void sort(long[] list, int left, int right) {
		final int fleft = left;
		final int fright = right;
		final long[] flist = list;
		// wenn die zu sortierende Liste mehr als ein Element hat...
        if(fleft < fright) {
			// Liste teilen
			final int pivot = (fleft + fright) / 2;

			// sort für beide Teilelisten aufrufen
			// neuen Thread für beide rekursive Aufrufe erstellen
			Runnable lRunnable = new Runnable() {
				public void run() {
					 sort(flist, fleft, pivot);
				}
			};
			Runnable rRunnable = new Runnable() {
				public void run() {
					 sort(flist, pivot + 1, fright);
				}
			};
			Thread lThread = new Thread(lRunnable);
			Thread rThread = new Thread(rRunnable);
			lThread.start();
			rThread.start();
			
			// auf beide Threads warten
			//for (;;) {
				try { lThread.join(); /*break;*/ }  catch (InterruptedException e) {}
			//}
			//for (;;) {
				try { rThread.join(); /*break;*/} catch (InterruptedException e) {}
			//}

			// beide Teillisten zusammenfügen
			merge(list, left, pivot + 1, right);
        }
    }

	// fügt zwei Teillisten sortiert zusammen
    private static void merge(long[] list, int leftPos, int rightPos, int rightEnd ) {
        // Array, in das Teillisten sortiert eingefügt werden
		long[] tmpArray = new long[list.length];

		int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        // solange beide Teillisten noch Elemente haben...
        while( leftPos <= leftEnd && rightPos <= rightEnd )
			// wenn nächstes Element der linken Liste kleiner als das der rechten ist...
            if(list[leftPos] <= list[rightPos] )
				// einfügen
                tmpArray[tmpPos++] = list[ leftPos++ ];
            else
				// ansonsten aus der rechten Liste einfügen
                tmpArray[ tmpPos++ ] = list[ rightPos++ ];

		// restliche Elemente einfügen
        while(leftPos <= leftEnd)
            tmpArray[tmpPos++] = list[leftPos++];

        while(rightPos <= rightEnd)
            tmpArray[tmpPos++] = list[rightPos++];

        // temporäres Array zurückkopieren
        for( int i = 0; i < numElements; i++, rightEnd-- )
            list[rightEnd] = tmpArray[rightEnd];
    }
}
